import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/7 15:30
 * @description 层序遍历 BFS
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.push(root);

        TreeNode t = null;
        while (!deque.isEmpty()) {
            t = deque.pollFirst();
            // 先将右节点加入，再将左节点加入，那么最后一个为底层的最左节点
            if (t.right != null) {
                deque.addLast(t.right);
            }
            if (t.left != null) {
                deque.addLast(t.left);
            }
        }
        return t.val;
    }
}
